Linear Data Structure

Posted on Edited on In

Linear Structures

Once an item is added, it stays in that position relative to the other elements that came before and came after it. * stacks * queues * deques * lists

Stack abstract data type

  • Satck() return empty stack
  • push(item) return nothing
  • pop() return the item
  • peek() returns the top item from the stack but does not remove it.
  • isEmpty()
  • size()

The implementation is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Stack:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[len(self.items) - 1]

    def size(self):
        return len(self.items)

Queue abstract data type

  • Queue() return empty queue
  • enqueue(item)
  • dequeue()
  • isEmpty()
  • size()

The implementation is: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Queue:

    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self, item):
        self.items.insert(0, item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)

deque

A deque, also known as a double-ended queue, is an ordered collection of items similar to the queue

  • Deque() return empty deque
  • addFront(item)
  • addRear(item)
  • removeFront() return the item
  • removeRear() return the item
  • isEmpty()
  • size()

Lists

The Unordered List

A list is a collection of items where each item holds a relative position with respect to the others. More specifically, we will refer to this type of list as an unordered list.

  • List() creates a new list that is empty. It needs no parameters and returns an empty list.
  • add(item) adds a new item to the list. It needs the item and returns nothing. Assume the item is not already in the list.
  • remove(item) removes the item from the list. It needs the item and modifies the list. Assume the item is present in the list.
  • search(item) searches for the item in the list. It needs the item and returns a boolean value.
  • isEmpty() tests to see whether the list is empty. It needs no parameters and returns a boolean value.
  • size() returns the number of items in the list. It needs no parameters and returns an integer.
  • append(item) adds a new item to the end of the list making it the last item in the collection. It needs the item and returns nothing. Assume the item is not already in the list.
  • index(item) returns the position of item in the list. It needs the item and returns the index. Assume the item is in the list.
  • insert(pos,item) adds a new item to the list at position pos. It needs the item and returns nothing. Assume the item is not already in the list and there are enough existing items to have position pos.
  • pop() removes and returns the last item in the list. It needs nothing and returns an item. Assume the list has at least one item.
  • pop(pos) removes and returns the item at position pos. It needs the position and returns the item. Assume the item is in the list.

Implementation Linked Lists 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Node:
    def __init__(self, initData):
        self.data = initData
        self.next = None

    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def setData(self, newData):
        self.data = newData

    def setNext(self, newNode):
        self.next = newNode

class UnorderedList:
    def __init__(self):
        self.head = None

    def isEmpty(self):
        return self.head == None

    def add(self, item):
        temp = Node(item)
        temp.setNext(self.head)
        self.head = temp

    def size(self):
        count = 0
        current = self.head
        while current != None:
            current = current.getNext()
            count += 1

        return count

    def search(self, item):
        current = self.head
        found = False
        while current != None:
            if item == current.getData():
                found = True
                break
            else:
                current = current.getNext()

        return found

    def remove(self, item):
        current = self.head
        found = False
        previous = None

        while current != None:
            if item == current.getData():
                break
            else:
                previous = current
                current = current.getNext()

            if previous == None:
                self.head = current.getNext()
            else:
                previous.setNext(current.getNext())

Modify the append method to be O(1)

The Ordered List

The structure of an ordered list is a collection of items where each item holds a relative position that is based upon some underlying characteristic of the item.

  • OrderedList() creates a new ordered list that is empty. It needs no parameters and returns an empty list.
  • add(item) adds a new item to the list making sure that the order is preserved. It needs the item and returns nothing. Assume the item is not already in the list.
  • remove(item) removes the item from the list. It needs the item and modifies the list. Assume the item is present in the list.
  • search(item) searches for the item in the list. It needs the item and returns a boolean value.
  • isEmpty() tests to see whether the list is empty. It needs no parameters and returns a boolean value.
  • size() returns the number of items in the list. It needs no parameters and returns an integer.
  • index(item) returns the position of item in the list. It needs the item and returns the index. Assume the item is in the list.
  • pop() removes and returns the last item in the list. It needs nothing and returns an item. Assume the list has at least one item.
  • pop(pos) removes and returns the item at position pos. It needs the position and returns the item. Assume the item is in the list.

implement

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
from Node import Node

class OrderedList:
    def __init__(self):
        self.head = None

    def search(self, item):
        current = self.head
        while current != None:
            if current.getData() == item:
                return True
            else:
                if current.getData() > item:
                    return False

            current = current.getNext()

        return False

    def add(self,item):
        current = self.head
        previous = None
        stop = False
        while current != None and not stop:
            if current.getData() > item:
                stop = True
            else:
                previous = current
                current = current.getNext()

        temp = Node(item)
        if previous == None:
            temp.setNext(self.head)
            self.head = temp
        else:
            temp.setNext(current)
            previous.setNext(temp)


    def isEmpty(self):
        return self.head == None

    def size(self):
        current = self.head
        count = 0
        while current != None:
            count += 1
            current = current.getNext()

        return count

about the do-while loop in Python, there is no do-while loop in Python, so when can just do as this:

1
2
3
4
while True:
    stuff()
    if not condition():
        break

equals: 

1
2
3
do {
    stuff()
} while (condition())